package DynamicProgramming;

public class 整数拆分 {
    public int integerBreak(int n) {
        // 贪心
        if (n <= 3) return n - 1;
        int x = n / 3;
        int y = n % 3;
        if (y == 0) return (int) Math.pow(3, x);
        if (y == 1) return (int) Math.pow(3, x - 1) * 4;
        return (int) Math.pow(3, x) * 2;

        // 动态规划
        /*int[] dp = new int[n + 1];
        dp[2] = 1;
        for (int i = 3; i <= n; i++) for(int j = 1; j <= i-j; j++) dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
        return dp[n];*/
    }
}
